package cn.xkai.exercise.c;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @description: 寻找重复的子树
 * 思想：递归存储每个子树到哈希表中
 * @author: kaixiang
 * @date: 2022-07-28
 */
public class Solution103 {
    List<TreeNode> ans = new ArrayList<>();
    HashMap<String, Integer> map = new HashMap<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        serial(root);
        return ans;
    }

    public String serial(TreeNode treeNode) {
        if (treeNode == null) {
            return "#";
        }
        String serialString = treeNode.val + "," + serial(treeNode.left) + "," + serial(treeNode.right);
        map.put(serialString, map.getOrDefault(serialString, 0) + 1);
        if (map.get(serialString) == 2) {
            ans.add(treeNode);
        }
        return serialString;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
